/*Copyright (C) 2013-2023 LZE*/
#include<bits/stdc++.h>
#define fo(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
#define INF 0x7fffffff
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef const long long cll;
const int N = 500010;
const int M = 1000010;
ll n, m, s;
struct GraphNode {
    ll to, w;
    GraphNode() {}
    GraphNode(cll &x, cll &y) : to(x), w(y) {}
    bool operator < (const GraphNode &x) const {
        return w > x.w;
    }
} p;
vector<GraphNode> G[M];
priority_queue<GraphNode> q;
ll dis[N];
bool vis[N];
int main() {
    scanf("%lld%lld%lld", &n, &m, &s);
    ll x, y, w;
    for(ll i = 1; i <= m; i++) {
        scanf("%lld%lld%lld", &x, &y, &w);
        G[x].push_back(GraphNode(y, w));
    }
    for(ll i = 0; i <= n; i++) dis[i] = INF;
    dis[s] = 0;
    q.push(GraphNode(s, 0));
    while(!q.empty()) {
        p = q.top(); q.pop();
        if(vis[p.to]) continue;
        vis[p.to] = true;
        for(ll i = 0; i < G[p.to].size(); i++) {
            GraphNode t = G[p.to][i];
            if(dis[t.to] > dis[p.to] + t.w) {
                dis[t.to] = dis[p.to] + t.w;
                q.push(GraphNode(t.to, dis[t.to]));
            }
        }
    }
    for(ll i = 1; i <= n; i++) printf("%lld ", dis[i]);
    printf("\n");
    return 0;
}